BSTJ 55: 7. September 1976: Analysis of Toll Switching Networks. (Krupp, R.S.)

Copyright © 1976 American Telephone and Telegraph Company

The Bell System Technical Journal

Vol. 55, No. 7, September 1976

Printed in U.S.A.

Analysis of Toll Switching Networks

By R. S. KRUPP
(Manuscript received December 26, 1975)

Two techniques are introduced for extending C. Y. Lee's method of
switching network analysis to cases of toll-type networks. The methods
avoid certain inconsistent independence assumptions which would other-
wise be a source of inaccuracies. One method partitions the Lee graph in a
special way, while the other uses a lemma that characterizes the generating
function of an average network property. Examples are worked for three-
stage networks and a model of the No. 4 ESS.

I. INTRODUCTION

In a well-known 1955 article, 1 C. Y. Lee introduced simplified
methods for the analysis of switching network characteristics, such
as blocking probability. Using a probability linear-graph (hereafter
called Lee graph) to represent the network and an assumption of
independent link occupancies, he described ways to quickly obtain
approximate expressions in many cases of interest. As an example of
possible inaccuracy, Lee pointed out a three-stage network that is
known to be nonblocking but is assigned a nonzero blocking prob-
ability by his method.

The present work introduces two different techniques for extending
Lee's method to avoid certain inconsistent independence assumptions,
which are the source of the inaccuracies he noted. The extended
methods will, for instance, reproduce M. Karnaugh's more accurate
expression 2 for blocking probability of a three-stage network, but with
less mathematical labor. When applied to a "generalized" three-
stage network that can model the No. 4 ess, 3 the techniques yield
formulas that greatly simplify expressions currently in use. The
appendix lists a computer routine to calculate blocking for the case of
generalized three-stage networks.

II. FIRST METHOD

2.1 Generalized three-stage switching network

Consider first a "generalized" three-stage switching network, as
indicated schematically in Fig. 1. The solid circles in the first and last

843

Tx A

l^Sw ^^i(i^\^

>/ 1

r j><^

M ^>

\ A

\ >r \ i' /

. \

Fig. 1 — Generalized three-stage switching network.

stages denote ordinary nonblocking switches, of sizes N X M and
M X L, respectively, such as crosspoint arrays or time-slot inter-
changers. The open circles in the middle stage, however, stand for
switches that could block. Such a switch might, at a given time, have
only a probability, rather than a certainty, of being able to connect a
given pair of A- and B-links incident on it. This could model addi-
tional stages of switching network, such as the time-shared space-
division stages in the No. 4 ess. 3 An independent blocking probability
Q is assigned to each middle-stage switch. We use the notation
Q = 1 — Q to indicate the corresponding transmission probability.
The overbar denotes the probabilistic complement in all formulas
that follow.

The Lee 1 graph in Fig. 2 shows all paths of the three-stage network
that might be used to connect one call between a specified pair of
terminations. Besides that pair, there are E = N — 1 other input
terminations at the first-stage switch and F = L — 1 other output
terminations at the last-stage switch. If we assign occupancy prob-
abilities P and R, respectively, to input and output terminations
other than the designated pair, the A- and B-links will have average
occupancies P = PE/M and R m RF/M.

If the first stage is a concentrator with E > M, it would be mathe-
matically inconsistent to assume that the termination occupancies P
were independent. In fact, that would imply a nonzero probability
P E of handling E calls on only M links. It would not be inconsistent
to assume a -priori that the A-link occupancies Po were independent
when E ^ M. A similar discussion applies to the last stage for the
case F > M. Assuming that all probabilities P , Q, and R are inde-
pendent, the transmission probability for any single path becomes a
product PoQRo of transmission probabilities for each of its portions.

Fig. 2 — Lee graph of generalized three-stage network.
844 THE BELL SYSTEM TECHNICAL JOURNAL, SEPTEMBER 1976

Then the blocking probability for the network is just the product of
blocking probabilities for each of the M independent paths.

itb = (1 - PoQRoV 1 = PoQRo . (1)

If there is expansion in the first stage, with M > E, it would be
mathematically inconsistent to assume that the link occupancies Po
were independent. Indeed, that would imply a nonzero probability
Pq of busying all M links with at most E calls. It would not be in-
consistent to assume that the termination occupancies P were inde-
pendent when M ^ E. A similar discussion applies to the last stage
for the case M > F. In the boundary case E = M, assuming random
connections through the switch, we find that each kind of independence
assumption (link or termination) implies the other with P = Po, and
neither is inconsistent. Whether either assumption agrees with ob-
served behavior of traffic is a difficult question that will not be ex-
plored here.

2.2 Toll-neutral case

To shorten our terminology, we will name the case E > M "local,"
the case E < M "toll," and the case E = M "neutral." To emphasize
the distinction, we cite the celebrated "Clos-type" network. Clos 4
showed that a pure three-stage network (the case Q = 0) will be non-
blocking when M > E + F. But (1) can vanish only when P and R
do. The contradiction arises from using the link independence assump-
tions in a toll case. The local case will not be considered in this study.

No matter what assumptions are appropriate, the event of having K
busy A-links is the same as that of K busy input terminations, whence
they have equal probability. In the toll case this is

= (^)P*(1-P) M , (2)

since there are (£) ways to choose K busies plus E — K idles among E
terminations, and each arrangement occurs with probability
P A '(1 — P) E ~ K , when termination occupancies P are independent.
Assuming that all probabilities P, Q, and Ro are independent, trans-
mission probability for any single path containing an idle A-link is
QR , and blocking probability for all M — K idles becomes
(1 - QR ) M - K . Multiplying by the probability of M - K idles (2)
and summing over all ^ K ^ E yield

*b = E (| ) PHI - P) E - K d - QRo) M ~ K , (3)

the network blocking probability for the "toll-neutral" case E^M = F,

TOLL SWITCHING NETWORKS 845

TT.-l

Fig. 3 — Graph of toll-neutral network.

as opposed to the "neutral-neutral" case E = M = F given by (1),
in the form

t b = (1 - PQR) M - PQR M . (la)

We have set R = R since F = M and P = P since E = M.
By binomial theorem, the sum (3) is

itb - (1 - QRo) M - E (l - PQRo) E , (4)

but this may be derived by a more direct route. To see this, we note
that there is a minimum of I = M — E idle A-links, no matter what
the status of the E input terminations. Let us set aside i" such idle
A-links in Fig. 3, denoting them by dashed lines. This partitions Fig. 2
into two parallel graphs, the upper one with / independent paths and
all A-links idle, and the lower one with E independent paths. The
lower graph is just the neutral case so that, mirabile dictu, its A-links
have independent occupancies P if its input terminations do. Thus,
blocking probability for the lower graph is given by (1), with Pq re-
placed by P and M by E. Blocking for the upper graph is just
(1 — QRo) 1 , as noted before (3). Network blocking (4) is then the
product of these two terms.

2.3 Toll-toll case

There remains only the "toll-toll" case E ^ M ^ F, with the as-
sumption of independent occupancies P and R for input and output
terminations. The argument leading to (2) may be repeated to yield
the probability

wam = (!)( y) px 0- ~ P) E ~ x R Y 0- - R) F ~ Y (5)

of having X busy A-links and Y busy B-links.

The pure three-stage switch (Q = 0) blocks only if none of the M—X
idle A-links matches any of the M — Y idle B-links. There are (y)
ways to arrange the idle B-links, but only ( M 'I y ) of these match all
M — Y idles to the X busy A-links. Thus, assuming all arrangements

846 THE BELL SYSTEM TECHNICAL JOURNAL, SEPTEMBER 1976

are equally probable, the mismatch blocking probability becomes

= {m- y)/{y ) = xlYl / Ml & + Y - M > ! <®

TXY

Multiplying (5) by (6) and summing over ^ X ^ £ and ^ Y ^ F
yields the overall network blocking probability

7TB = X tab(X, Y)ttxy- (7)

X. Y

Karnaugh 2 has performed this sum, using binomial theorem first
on the X-sum to obtain

''-(u-,W)v( a Y-T M )'~ v *-'r*»

and then on the F-sum to yield the blocking

TB ~ M\{E + F-M)\ F R (1 FH) (J)

in closed form. Now tt B in (9) appears to be the product of a "com-
binatorial" factor (m- F )/(f) and a "probabilistic" one. A direct
derivation will help to bring out their origins.

Again, there are at least I = M — E idle A-links and J = M — F
idle B-links. We set these aside in the Lee graph in Fig. 4, denoting
them by dashed lines, as before. No matching of dashed A- and B-links
is shown in the figure, since this could not correspond to a blocked state
of the network. There arc E solid A-links, corresponding to the neutral
case, so that we can assume independent occupancies P = P for them.
Similarly, the F solid B-links will have independent occupancies R.

Figure 4 clearly partitions Fig. 2 into three parallel graphs. The top
graph has / independent paths and its blocking is obviously R 1 . The
bottom graph has J independent paths, and its blocking is P J . The
middle graph has H = M-I-J=E-\-F-M independent
paths, each with transmission probability PR, so that its blocking is

I

Fig. 4 — Graph of toll-toll three-stage network.

TOLL SWITCHING NETWORKS 847

(1 — PR) M ~*~ J . The product of these three blocking probabilities,

tp = p j r*M m -'- j , (10)

is the blocking for the network configuration in Fig. 4 and is also the
"probabilistic" portion of ttb in (9).

There are (30 ways to arrange the dashed B-links, but only ( M J~ J )
of these match all J dashed B-links to solid A-links. If all arrangements
are equally likely, the quotient (5)/ (30 is the probability of the
"blockable" configuration in Fig. 4. This accounts for the "combina-
torial" portion of tb in (9), which is in fact the blocking at full oc-
cupancy P = R = 1. Note that, if M > E + F, then (E + F - M)\
is infinite and ttb vanishes in (9), consistent with Clos' result.

2.4 Generalized toll-toll case

Even if Z of the M - X idle A-links match Z of the M — Y idle
B-links in (5), a generalized three-stage network may still block, with
probability Q z , for P, Q, and R independent. There are (y) ways to
arrange the M — Y idle B-links, but only ( m z x )(m-*-z) ways to
match just Z of them to M — X idle A-links and the rest to the X
busy A-links. For equally likely arrangements, then, the probability
of a Z-match becomes

irz

-(*i X )U -*-.)/(?)• 01)

The overall network blocking probability now is the sum over X, Y,
and Z of the product of (5), (11), and Q z ,

t b = E Q z tab(X, Y)tz(X, Y). (12)

X.Y.Z

As an example, 3 M = 128 and L = N = 105 in the No. 4 ess so that
E = F = 104 and / = / = 24. This makes ir B in (12) the sum of
302,845 nonzero terms.

As discussed previously, a more direct derivation of blocking
probability tb may be prosecuted for the generalized three-stage
network. We set aside / idle A-links and J idle B-links as dashed lines
in the Lee graph, Fig. 5. This time there may be some matching of V
dashed A- and B-links, for ^ V ^ I, J. Figure 5 partitions Fig. 2
into four parallel graphs with I — V, V, J — V, and H + V = M
— I — J + V independent paths, respectively, to yield blocking
probabilities of (1 - QRy- v , Q v , (1 - PQy~ v , and (1 - PQR) H+V
as discussed earlier.

There are (30 ways to arrange the J dashed B-links but only
(y)G - v) ways to match just V of them to the / dashed A-links and

848 THE BELL SYSTEM TECHNICAL JOURNAL, SEPTEMBER 1976

Fig. 5 — Graph of toll-toll generalized three-stage network.

the rest to the E solid A-links. Thus, the probability of a 7-match is

(I\( E \ //M\_ I\J\E\F\/M\V\

wv ~\ V)\J - V)/ \j J' (I- V)\(J - V)\(H + 7)! {i6)

if all arrangements have equal likelihood. This is multiplied by the
blocking probability for a network with V matches, as in Fig. 5, and
summed over V to yield the overall network blocking probability

tb = e r V Q v a - pQy- v a - qry- v (i - pqr) h+v . (14)

V

III. SECOND METHOD

For the example of the No. 4 ess, tb in (14) is the sum of 25 non-
zero terms. It does not appear to be possible to perform the 7-sum
and reduce (14) to a single term; however, we shall see that tb does
have a simple one-term generating function, as well as one-term
operator-product expressions.

3.7 The generating function

It is possible to perform the X-, Y-, and Z-sums in (12), and thus
reduce tb to the simpler form (14). While tedious, this exercise is also
highly instructive. Writing out (5) and (11) at length in (12) yields

TB = x$z Q (E-X)\ " (F- Y)\ P Txrz ' (15)

where a = P, and /3 = R and the last factor is

= E\F\/M\Z\

Txyz ~ (M - X - Z)\(M - Y - Z)\(X + Y + Z - M)\

E\F\(M\(M - Z\( X \ , lfi .

= 14¥\Z)\ X )\M-Y-Z) (16)

TOLL SWITCHING NETWORKS 849

Substituting the following identities into (15),

(M — X) . E _ x qM-E m-x - di a M-x
(E — X) I

(17)

( ( ^_ Y^; P-* = df~ F P M ~ Y = dft"- Y , (18)

where d a and dp are the a- and /3-derivatives, yields

s '-5(jf-r-*)«V- r - < 20 >

We should note that, formally, a and /3 are independent variables,
which are set equal to P and R only after all differentiations are per-
formed. Thus, d a and dp do not act on P and R.
By binomial theorem, the sum in (20) is just

S Y = p z R M - x ~ z (p + R) x ,

which reduces (19) to

EW* /M\

** = f£ «w 5 w( z ) * (21)

& = l( M ^ Z ) P*a*-*i2"-*-*(/3 + R) x . (22)

Similarly, the sum in (22) may be performed to get Sx = a z y M ~ z for
y = aR + pP + P# and reduce (21) to

7T/J

= w 8 ^? u) •'W"' < 23 >

The sum in (23) is just (a/3Q -f- y) M , by a third application of bi-
nomial theorem, whence it becomes

itb = -^ dffiiaPQ + aR + {3P + PR) M

= Q Bi(aQ + P) J {af$Q + T )* (24)

The forms (24) are about the closest we can get tb to a simple
closed expression. Leibniz' rule for the derivatives of a product will
give (24) the form

tb = £ T V Q v (aQ + P) J - V (PQ + RY- v (aPQ + y)"+ v , (25)

850 THE BELL SYSTEM TECHNICAL JOURNAL, SEPTEMBER 1976

with ttv as in (13). Substituting a = P and /3 = R will now reduce (25)
to (14), since, for example,

aQ + P = P(l - Q) + 1 - P = 1 - PQ (26)

a/3Q + 7 = 0(oQ + P) + B(a + P)

- 22(1 - PQ) + 1 - 5 = 1 - PQR. (27)

What is particularly illuminating in the preceding calculation is
step (24). It says that t b (I, J), the blocking probability for a network
with I excess A-links and J excess B-links, is a differential coefficient
of "something." To make this idea more precise, we construct the
corresponding generating function G. Multiplying (24) by (j)U*(j)W j
and then summing over all ^ /, J ^ M yield the form

'-bGMI)*™*

(28)

- £ TT -TT *&MQ + «fl + /SP + Pfl) M -

By Taylor's theorem, the second line is just

(? = [([/ + p)(W + R)Q + (C/ + P)/2 + ("FT + R)P + P72] M
= L(U + 1)(W + 1) - (U + P)(TT + R)Q2 M

= & + ^^ + ^ [ x - ( x - FTlX 1 " VTT ) °r

(29)

Thus, itb(I, J) can be obtained by expanding (29) in powers of U and
W, then inspecting the coefficient of U T W J . In practice, we get the
coefficient by differentiating / times in U and J times in W, then
setting U = W = 0. But this is exactly equivalent to the steps leading
from (24) to (14).

3.2 Fundamental lemma

In the preceding section, it was shown that blocking probability tb
could be obtained quickly and directly from a generating function G,
rather than through an argument involving a four-way partition of
the Lee graph. If we could now obtain G directly, without steps (5),
(11), (12), and (15) to (24), a great deal of effort might be saved. The
structure of G is indeed determined by the following lemma, which has
surprisingly little to do with switching networks.

We idealize the network as a "black box," as in Fig. 6, on which a
certain set of M "trunks" are terminated. These are assumed to have

TOLL SWITCHING NETWORKS 851

M

P

Fig. 6 — •Network idealized as black box.

independent occupancy probabilities P, except that some number
I ^ M of the trunks are "dead" or disconnected, with zero occupancies.
Associate with the black box some quantity A (if), a function of the
number K of busy terminations among the E = M — I "active"

trunks. By using (2), we find the average value of A to be

ar(J, P) m £ ( M R 7 ) P*(l - P) M - Z - K HK).

(30)

We have assumed that the M trunks are interchangeable, in the sense
that A, and hence ir, does not depend on which I of the M are dead.

Fundamental Lemma: The generating function for ir(I,P) is written
in terms of tt(0, P) as

G - Z (f ) U'wd, P) = (U+ 1)"* (0, ir ^ rT )

(31)

Formal Proof: Substitute (30) into (31) and use binomial theorem to
perform the sum over ^ 7 ^ M.

Informal Proof: Suppose that each trunk has an independent proba-
bility X of being active, and hence X = 1 — X of being dead. Then the
average value of it is just

it = £ ( M j ) X M - 7 (1 - X)M7, P). (32)

On the other hand, each trunk carries an average load of \P erlangs,
independent of the others, so that ft = 7r(0, XP). We now define
U = X/X, which yields X = 1/(U + 1), and set G = (U + l) M x to
transform (32) into (31). The model of "dead trunks" is invoked only
to validate the mathematical relation (31), of course, and need not
accord with observed behavior.

An obvious application of the lemma is to let the black box be a
switching network and -k be its blocking probability tb for some pair
of terminations. As an example, consider the "toll-neutral" case of
the generalized three-stage network, with E ^ M = F. Let the M
trunks be terminated on the same first-stage switch as the input

852 THE BELL SYSTEM TECHNICAL JOURNAL, SEPTEMBER 1976

termination of the pair whose blocking is sought. Then 1 = corre-
sponds to the neutral case E = M, for which (1) is valid with Po = P.
Now the generating function becomes

G - (CT + D M [l - (l - ir q 7I ) QR J'

= [£/ + 1 - (U + P)QRo1 M . (33)

Differentiating / times at U = yields the blocking

tb(I,P) -W/Jl(*)

= (1 - QR y(l - PQ&o)"-', (34)

which is the same formula as (4). A bare minimum of knowledge about
the network structure, just formula (1), was thus sufficient to deter-
mine blocking probability.

The "toll-toll" case, E ^ M ^ F of the generalized three-stage
network, requires an iterated form

G - £ ( M j ) U' (»\ W'*(I, P;J, R)

-5(/) Df *( / -^FTl)< !|r + » P

= (U + 1)*<W + l)-» (o, jj^j-,0, ^-j ) (35)

of the lemma. For n = M trunks terminated on the same last-stage
switch as the output termination of the pair whose blocking is sought,
we see that I = J = is the neutral case E = M = F, with ttd given
by (la). Thus, substituting (la) into (35) yields a generating function

g = (u + i)*OP + d- [i - (i - ^)(i - ^ ) q] m ,

(36)
which is the same as (29) . The blocking becomes

« = i'MO/I ! ( M j ) J I ( " ) = dig/ J ! ( ^ ) (37)

,-OT + l)- [1.(1-^)0]'

[i-^i-FT-OC' (38)

TOLL SWITCHING NETWORKS 853

and applying Leibniz' rule for the derivatives at W = again yields

(14) -
Another approach is to observe that we have already "differentiated

off" / terminations in the "toll-neutral" case. Applying the lemma

once more to (34), we can construct the generating function g in (38)

at once and then "remove" the J spare output terminations as in (37)

to obtain blocking probability (14). Again, only (1) was needed to

specify the particular network under consideration.

3.3 Operator formulation

Lemma (31) may be "solved" for ir(I, P) by making a formal
expansion of its right side in terms of d, the P-derivative. Observing
that

e aP3pn m £ (f&p!. p» = £ (^ pn = ( e ap)n (39)

l 11 l t!

and hence A pa f(P) = f(AP), the generating function is

G - (U + 1) M ~ P MO, P) = t Q ( M 7 P9 ) U'HO, P). (40)

Equating powers of U in (31) and (40) yields the identity

,(/,P) = ( M 7 P3 ).(0,P)/(f), (41)

which we write out as an operator product

-(i- 3r ^r+i)*< / - 1 ' p) - w>

This has a simple and natural interpretation: "deloading operator"
1 — Pd/E serves to "remove" one of the E remaining terminations
represented in the expression ir(M — E, P) for any average network
property ir.

Of course, the validity of the mathematical manipulations above
must still be demonstrated. This hinges upon establishing convergence
of the operator expansion in (40), and hence the sum in /. But we note
that each factor of the form n — Pd will annihilate the corresponding
power P" in ir(0, P). Thus, if r is a polynomial of degree M at most,
as in (30), it is annihilated completely in all terms of (40) for which
/ exceeds M, and the expansion indeed converges, since the sum is
finite. In practical calculations of blocking probabilities or other

854 THE BELL SYSTEM TECHNICAL JOURNAL, SEPTEMBER 1976

formulas, the operator formulation (42) may not be as convenient to
use as direct differentiation of the generating function.

IV. SUMMARY AND DISCUSSION

Two techniques are introduced to extend C. Y. Lee's method to
switching networks of "toll" types denned in the text. Basically, these
have some expansion in the first stage or concentration in the last
stage, or both. The link independence assumptions of Lee's method
are inconsistent in such cases, which causes some inaccuracy.

The first of the two extension techniques partitions the Lee graph
into two or more smaller graphs, so that the independence assumptions
will be consistent within various portions. This is done by setting
apart the proper number of links that are known to be idle. The first
technique is applied to examples of three-stage networks, yielding a
result of Karnaugh's and a simplification of the expression used for
computing blocking for the No. 4 ess. To focus attention on the
methods, all examples worked out are blocking probabilities, but other
network averages may be treated similarly.

The second, and more general, technique makes use of a lemma that
characterizes the generating function of an average property for a
whole family of networks. In a sense, this technique is a counterpart
of the first, since it operates by attaching a sufficient number of idle
"phantom" terminations to the network to make the link independence
assumptions valid, instead of setting aside idle links. Then the gener-
ating function can be constructed from the resulting "neutral" case,
and the lemma, or an equivalent operator formulation, allows removal
of the excess terminations. Two of the three-stage network examples
are reworked to make a comparison of the two techniques.

V. ACKNOWLEDGMENTS

The author is grateful for comments and suggestions from Thomas
J. Cieslak, Frank K. Hwang, Elena M. Johnson, Joseph G. Kappel,
and Mary N. Youssef, and for assistance from Sheila R. Wiggins in
testing the program for calculating blocking probabilities.

APPENDIX

The Fortran subroutine listed in Table I calculates the blocking
probability itb given by (14) for the "toll-toll" case of the generalized
three-stage switching network. Cancelling among the nine factorials
in (13) yields an efficient calculation and minimizes the chance of
underflow or overflow. The routine is accessed by :

CALL BLOCK (/, P, J, R, M, Q, PI)

TOLL SWITCHING NETWORKS 855

Table I — Blocking probability subroutine

SUBROUTINE BLOCK (I, P, J, R, M, Q, PI)

K = M - I - J

L = MAX0(0, 1 + J - M)

PQ = 1.0 - (1.0 - P)*(1.0 - Q)

RQ = 1.0 - (1.0 - R)*(1.0 - Q)

SQ = 1.0 - (1.0 - R)*(1.0 - Q)*(1.0 - P)

A = 1.0

IF(L.GT.O) A = Q**L

A = A*PQ**(J - L)*RQ**(I - L)*SQ**(K + L)

B = A

C = Q*SQ/(PQ*RQ)

D = 1.0

LOW = L + 1

LIM = MIN0(I, J)

IF(LIM - L) 30, 20, 10
10 DO 15 N = LOW, LIM

A = A*C*FLOAT((I - N + 1)*(J - N + l))/FLOAT((K + N)*N)

B = B + A
15 D = D*FLOAT(K + L + N)/FLOAT(M + N - LIM)
20 PI = B*D
30 RETURN

END

and, referring to Fig. 1, the arguments are:

I = M — E = M — N + 1 minimum number of idle A-links

J = M — F = M — L -\- 1 minimum number of idle B-links

M number of center-stage switches

P average occupancy probability of input terminations

Q blocking probability of center-stage switches

R average occupancy probability of output terminations

PI returns the calculated value of itb.

Independence is assumed for all P, Q, and R.

REFERENCES

1. C. Y. Lee, "Analysis of Switching Networks," B.S.T.J., 34, No. 6 (November

1955), 1287-1315.

2. M. Karnaugh, unpublished work, August 1954.

3. H. E. Vaughan, "An Introduction to No. 4 ESS," paper presented at the Inter-

national Switching Symposium, Cambridge, Massachusetts, June 6, 1972.

4. C. Clos, "A Study of Non-Blocking Switching Networks," B.S.T.J., 32, No. 2

(March 1953), 406-424.

856 THE BELL SYSTEM TECHNICAL JOURNAL, SEPTEMBER 1976